Computers and computer networks have changed society and are as much a part of modern culture as television and telephones. People are becoming increasingly connected to share and access information. This interconnectivity promotes improvements in the computing and communication infrastructure.
Much of this infrastructure was designed for entertainment or communication, but is being adapted to also deliver general data. The addition of general information and data transmission over the legacy infrastructure is restrained by the need for the infrastructure to continue its initial functions. Most major entertainment and communication channels now include computer networking capabilities.
Similarly, many traditional networks transmit both raw data and real-time data such as voice over internet protocol (VoIP) as well as other streaming data with strict time constraints. Real-time data streams have strict time constraints but have lower reliability requirements, while other data does not have the time constraints of real-time data, therefore allowing robust and more reliable transmissions.
The Point-to-Point protocol (PPP), RFC 1661 dated July 1994, is a data link protocol and typically provides dial up access over analog or digital transmission lines. PPP provides features including, authentication, error detection, multiple protocol support, and negotiation of IP addresses at connection time.
PPP comprises three main features. It provides a framing method to delineate the end of one frame and the beginning of the next one, in order to handle error detection. It also provides a Link Control Protocol (LCP) for establishing and testing lines, negotiating options, and closing lines. And last, PPP provides a way to negotiate network layer options independent of the network layer protocol to be used.
PPP is commonly used as the data link protocol between a user and an Internet Service Provider (ISP) or access point. For example, a user may call an ISP through a modem with a personal computer. After the ISP's modem receives the call and establishes a physical connection, the personal computer may send LCP packets in the payload field of one or more PPP frames. In this regard a session may be negotiated, and the PPP parameters may be established for the session. After session negotiation and establishment of PPP parameters using LCP, an optional authentication phase may be entered.
Once the optional authentication phase is complete, a series of Network Control Protocol (NCP) packets may be sent to configure the network layer and assign an internet protocol (IP) address for the personal computer. At this point, the personal computer has become an Internet host and may send and receive IP packets. When the user has finished, different LCP control packets can be used to tear down the network layer connection and free the IP address, and also to shut down the data link layer connection. Finally, the personal computer hangs up the modem, releasing the physical layer connection.
PPP allows encapsulation of multi-protocol packets over layer two (L2) point-to-point links. For example, a PPP user may connect to a network access server (NAS) through dialup POTS, ISDN, ADSL, etc. and then run PPP over that connection. In the present example, the L2 and PPP both have an endpoint on the NAS.
PPP sessions may be tunneled through a packet network by Layer 2 Tunneling Protocol (L2TP) as described in RFC 2661. L2TP is loosely based on the Point-to-Point Tunneling Protocol (PPTP) and may be used by an Internet service provider (ISP) to enable the operation of a virtual private network (VPN) over a computer network such as the Internet.
The two main components that make up L2TP are an L2TP Access Concentrator (LAC), which is the device to physically terminate a call and the L2TP Network Server (LNS), which is the device that terminates the PPP session, and can even authenticate a PPP session. A PPP user may use an L2 connection to an access concentrator, and the concentrator can tunnel individual PPP frames to a LNS, allowing the packets to be processed in a different location than the circuit termination. This allows the circuit to terminate locally and reduce phone costs for the link.
Multiple PPP links may be coupled into a bundle using Multilink PPP (MLPPP) as described in RFC 1990 (PPP Multilink Protocol, August 1996). MLPPP provides a method to split, recombine and sequence datagrams across multiple logical data links.
According to RFC 1990, the goal of MLPPP is to coordinate multiple independent links between a fixed pair of systems, providing a virtual link with greater bandwidth than any of the constituent members. The aggregate link, or bundle, is named by the pair of identifiers for two systems connected by the multiple links. A system identifier may include information provided by PPP Authentication and information provided by LCP negotiation. The bundled links can be different physical links, as in multiple asynchronous lines, but may also be instances of multiplexed links, such as ISDN, X.25, or Frame Relay. The links may also be of different kinds, such as pairing dialup asynchronous links with leased synchronous links.
PPP sessions tunneled through L2TP traditionally forward all PPP frames, without knowledge of whether they are fragments in a multilink bundle or full PPP frames. Thus, for MLPPP sessions, the L2TP Access Concentrator (LAC) forwards all PPP packets from the links to the L2TP Network Server (LNS). It is then up to the LNS to fragment and reassemble fragments, and to forward the resultant layer three (L3) data.
Fundamental reasons for this form of operation in the past was (1) to offload the LAC, which may be a device packed with modems but with limited routing functionality, and (2) so that MLPPP sessions arriving from multiple LACs could be reassembled at a single location (e.g., the LNS).
A PPP link may fragment and interleave packets to manage traffic over the link. For example, PPP Link Fragmentation and Interleaving (LFI) utilizes the MLPPP protocol to fragment large frames into smaller frames on low-speed links in order to better the latency characteristics for delay-sensitive applications (such as voice) while using the same link for traffic which requires large data frames (such as browsing the web, uploading email, video transmission, etc.). LFI may utilize the MLPPP protocol even when not bundling multiple links.
U.S. Pat. No. 6,272,145, Malkin, describes a “Method and apparatus for communicating data across multiple communication links” In this, a L2TP is mentioned, together with a traditional method for forwarding link fragments from the LAC. Similarly, U.S. Pat. No. 6,763,018, Puthiyandyil, et. al., describes “PPP MultiLink in a Distributed Processing Environment” where the LNS is performing the fragmentation and reassembly of Multilink Frames.
Unfortunately, the traditional operation of performing fragmentation and reassembly for MLPPP at the LNS has negative consequences for the LFI application. For example, small packet fragments may be sent between the LAC and LNS, which statistically increases the probability of end to end packet loss as one lost or misordered fragment results in an entire lost frame. Also, small packets almost always have higher processing overhead for the amount of user-data transferred. Thus, the intervening network between an LAC and an LNS may be placed at a greater burden than if larger packets were sent.
Another negative consequence results since LFI MLPPP demands that Multilink fragments are delivered in order on a given link (RFC 1990, section 4.1). With fragmentation and reassembly at the LNS, there is a higher probability of misordering of MLPPP frames between the LAC and LNS, due to QoS (quality of service) or IP load balancing mechanisms (e.g., ECMP). L2TP provides its own, optional, packet sequencing method between the LAC and LNS to solve this problem, but this sequencing method does not come without overhead in terms of packet header size and processing for packets which are not sensitive to misordering.
U.S. Pat. No. 6,272,145 describes a “Method and apparatus for communicating data across multiple communication links” In this, a L2TP is mentioned, together with a traditional method for forwarding link fragments from the LAC. Similarly, U.S. Pat. No. 6,763,018 describes “PPP MultiLink in a Distributed Processing Environment” where the LNS is performing the fragmentation and reassembly of Multilink Frames.
Additionally, a drawback for conducting fragmentation at an LNS is that LFI relies on backpressure from physical interfaces to avoid queuing too many fragments to a link. Since the LNS is a physically separate device, it has no direct means of knowing when the physical link on the LAC is congested. As a result, when there is a large data packet to send, the LNS may immediately transmit all of the fragments of the packet even though those packets may be queuing on the LAC. Therefore, if a delay-sensitive packet arrives it may have to wait for all of the queued fragments to be sent. What is needed is an improved method and apparatus to provide link fragmentation and interleaving.